import java.util.*;

/**
 * 1765. 地图中的最高点
 * https://leetcode-cn.com/problems/map-of-highest-peak/
 */
public class Solutions_1765 {
    public static void main(String[] args) {
        int[][] isWater1 = {{0, 1}, {0, 0}};  // output: {{1, 0}, {2, 1}}
        int[][] isWater2 = {{0, 0, 1}, {1, 0, 0}, {0, 0, 0}};
        // output: {{1, 1, 0}, {0, 1, 1}, {1, 2, 2}}

        List<int[][]> inputs = new ArrayList<>();
        inputs.add(isWater1);
        inputs.add(isWater2);

        for (int[][] input : inputs) {
            int[][] result = highestPeak(input);
            System.out.println(Arrays.deepToString(result));
        }
    }

    /**
     * 解题思路：多源 BFS
     */
    public static int[][] highestPeak(int[][] isWater) {
        int row = isWater.length, col = isWater[0].length;
        LinkedList<int[]> queue = new LinkedList<>();
        // 四个方向：上、下、左、右
        int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (isWater[i][j] == 1) {
                    // 水域坐标入队列
                    queue.add(new int[]{i, j});
                    isWater[i][j] = -1;
                }
            }
        }
        int height = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] arr = queue.poll();
                // 设置高度
                for (int[] dir : direction) {
                    int m = arr[0] + dir[0];
                    int n = arr[1] + dir[1];

                    // 符合条件：未越界，未访问过
                    if (m >= 0 && m < row && n >= 0 && n < col && isWater[m][n] == 0) {
                        queue.add(new int[]{m, n});
                        // 为相邻区域设置高度
                        isWater[m][n] = height + 1;
                    }
                }
            }
            height ++;
        }
        // 原本设置的水域为 -1，需要还原为 0
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (isWater[i][j] < 0) {
                    isWater[i][j] = 0;
                }
            }
        }
        return isWater;
    }
}
